AB-words

Memory limit: 32 MB

Every sequence of small letters and (also the empty sequence) is called an ab-word. If is an ab-word and are integers such that then denotes the subword of consisting of the letters . We say that an ab-word is nice if it has as many letters as and for all the subword has at least as many letters as .

Now, we give the inductive definition of the similarity between nice ab-words:

• every two empty ab-words (i.e. words with no letters) are similar;
• two non-empty nice ab-words and are similar if they have the same length () and one of the following conditions if fulfilled:
  • , and and are similar ab-words and they are both nice,
  • there exists , , such that , are nice ab-words and
    • , are nice ab-words and is similar to and is similar to , or
    • , are nice ab-words and is similar to and is similar to .

A level of diversity of a non-empty set of nice ab-words is the maximal number of ab-words that can be chosen from in such a way that for each pair of chosen words, is not similar to .

Task

Write a program that:

• reads elements of from the standard input;
• computes the level of diversity of the set ;
• writes the result to the standard output.

Input

In the first line of the standard input there is a number of elements of the set , ; in the following lines there are elements of the set , i.e. nice ab-words (one word in each line); the first letter of every ab-word is the first symbol in line and there are no spaces between two consecutive letters in the word; the length of every ab-word is an integer from the range .

Output

In the first and only line of the standard output there should be written one integer — the level of diversity of .

Example

For the input data:

3
aabaabbbab
abababaabb
abaaabbabb

the correct result is:

2

Task author: Krzysztof Diks.